package com.demo.java.OD451_500.OD482;

import java.util.Scanner;
import java.util.HashSet;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【字符串拼接(E卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146407728
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // 获取输入的字符串和目标组合的长度
        String input_str = in.nextLine();
        String[] inputs = input_str.split(" ");
        String target_str = inputs[0];
        int target_len = Integer.parseInt(inputs[1]);

        // 如果目标长度大于字符串长度，直接返回0
        if (target_str.length() < target_len) {
            System.out.println(0);
            return;
        }

        // 使用回溯法生成所有符合条件的组合
        int[] flags = new int[target_str.length()]; // 标记字符是否已使用
        HashSet<String> result = new HashSet<>(); // 存储不重复的结果
        String temp = "";

        // 开始回溯
        backtrack(target_str, target_len, temp, result, flags);

        // 输出结果的大小，即满足条件的组合数量
        System.out.println(result.size());
    }

    // 回溯法，生成所有符合条件的组合
    public static void backtrack(String origin_strs, int length, String temp, HashSet<String> result, int[] flags) {
        // 当当前组合的长度达到目标长度时，加入结果集合
        if (temp.length() == length) {
            result.add(temp);
            return;
        }

        // 遍历每个字符，进行递归选择
        for (int i = 0; i < origin_strs.length(); i++) {
            // 每个字符只能使用一次且相同字符不能相邻
            if (flags[i] == 1 || (temp.length() > 0 && temp.charAt(temp.length() - 1) == origin_strs.charAt(i))) {
                continue; // 如果字符已经使用或与上一个字符相同，跳过
            }

            flags[i] = 1; // 标记字符已使用
            // 递归生成下一步的组合
            backtrack(origin_strs, length, temp + origin_strs.charAt(i), result, flags);
            flags[i] = 0; // 回溯时恢复标记
        }
    }
}